2010년07월24일 9번
[과목 구분 없음] 다음 그래프를 너비 우선 탐색(Breadth First Search BFS), 깊이 우선 탐색(Depth First Search DFS) 방법으로 방문할 때 각 정점을 방문하는 순서로 옳은 것은? 단, 둘 이상의 정점을 선택할 수 있을 때는 알파벳 순서로 방문한다. (순서대로 BFS, DFS)
- ① A-B-F-C-E-D, A-B-C-D-E-F
- ② A-B-C-D-E-F, A-B-F-C-E-D
- ③ A-B-F-C-D-E, A-B-C-D-E-F
- ④ A-B-C-D-E-F, A-B-C-D-F-E
(정답률: 53%)
문제 해설
BFS: A-B-F-C-D-E, DFS: A-B-C-D-E-F
BFS는 너비를 우선으로 탐색하기 때문에 A-B-F-C-D-E 순서로 방문하게 된다. 즉, A에서 시작하여 인접한 정점인 B와 F를 먼저 방문하고, 그 다음으로 C를 방문하고, D와 E를 마지막으로 방문하게 된다.
DFS는 깊이를 우선으로 탐색하기 때문에 A-B-C-D-E-F 순서로 방문하게 된다. 즉, A에서 시작하여 인접한 정점인 B를 먼저 방문하고, B에서 인접한 정점인 C를 방문하고, C에서 인접한 정점인 D를 방문하고, D에서 인접한 정점인 E를 방문하고, E에서 인접한 정점인 F를 마지막으로 방문하게 된다.
따라서 정답은 "A-B-F-C-D-E, A-B-C-D-E-F"이다.
BFS는 너비를 우선으로 탐색하기 때문에 A-B-F-C-D-E 순서로 방문하게 된다. 즉, A에서 시작하여 인접한 정점인 B와 F를 먼저 방문하고, 그 다음으로 C를 방문하고, D와 E를 마지막으로 방문하게 된다.
DFS는 깊이를 우선으로 탐색하기 때문에 A-B-C-D-E-F 순서로 방문하게 된다. 즉, A에서 시작하여 인접한 정점인 B를 먼저 방문하고, B에서 인접한 정점인 C를 방문하고, C에서 인접한 정점인 D를 방문하고, D에서 인접한 정점인 E를 방문하고, E에서 인접한 정점인 F를 마지막으로 방문하게 된다.
따라서 정답은 "A-B-F-C-D-E, A-B-C-D-E-F"이다.
